/**
 * @param {string} s
 * @return {string}
 */

var longestPalindrome = function (s) {
    const dp = []
    // 给定字符串的长度
    const len = s.length
    // 初始化二维数组
    for (let i = 0; i < len; i++) {
        dp[i] = []
    }

    // 初始化最长回文子串的两个端点值
    let st = 0, end = 0
    // 处理一个字母字符串
    // 初始化单个字母的回文子串，也是边界
    for (let i = 0; i < len; i++) {
        dp[i][i] = true
    }
    // 处理两个字符的字符串
    // 这里为了降低题目的复杂度，作者预先对悬念比较小的 s[i][i + 1] 也做了处理。将两个相连的相同的字母所对应的 dp[i][i + 1] 设为 true
    for (let i = 0; i < len - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true
            st = i
            end = i + 1
        }
    }
    // n 代表子串的长度，从3开始递增
    for (let n = 3; n <= len; n++) {
        // 下面的两层循环，用来实现状态转移方程
        for (let i = 0; i <= len - n; i++) {
            // 字符串最后一个索引
            let j = i + n - 1
            if (dp[i + 1][j - 1]) {
                // 若定位到更长的回文子串，则更新目标子串端点的索引值
                if (s[i] === s[j]) {
                    dp[i][j] = true
                    st = i
                    end = j
                }else{
                    dp[i][j] = false
                }
            }
        }
    }
    return s.substring(st, end + 1)
};